package 栈;

import java.util.HashMap;
import java.util.Stack;

/**
 * 20.Valid Parentheses（有效的括号）
 * https://leetcode-cn.com/problems/valid-parentheses/solution/
 *
 * Given a string containing just the characters '(', ')', '{', '}', '[' and ']',
 * determine(确定) if the input string is valid.
 *
 * An input string is valid if:
 *
 * Open brackets(括号) must be closed by the same type of brackets.
 * Open brackets must be closed in the correct(正确) order(顺序).
 * Note that an empty string is also considered valid.
 *
 * Example 1:
 *
 * Input: "()"
 * Output: true
 * Example 2:
 *
 * Input: "()[]{}"
 * Output: true
 * Example 3:
 *
 * Input: "(]"
 * Output: false
 * Example 4:
 *
 * Input: "([)]"
 * Output: false
 * Example 5:
 *
 * Input: "{[]}"
 * Output: true
 */

public class E_20_有效的括号 {
    /**
     * 栈：使用栈解决
     * 1.如果是左括号，将其入栈
     * 2.如果是右括号，则分情况
     *   a.如果栈不空，且出栈元素与其匹配，则继续遍历
     *   b.如果栈为空，则返回false
     *   c.如果栈不空，且出栈元素无法匹配，则返回 false
     *
     * Tip：维护一个HashMap保存括号键值对
     */
    static HashMap<Character, Character> single = new HashMap();
    static {
        single.put('{', '}');
        single.put('(', ')');
        single.put('[', ']');
    }
    public static boolean isValid1(String s) {
        Stack<Character> stack = new Stack<>();
        int length = s.length();
        for (int i = 0; i < length; i++) {
            char bracket = s.charAt(i);
            if (single.containsKey(bracket)) {
                stack.add(bracket);
            } else {
                if (stack.isEmpty()) { return false; }
                if (bracket != single.get(stack.pop())) { return false; }
            }
        }
        return true;
    }

    /**
     * 使用字符串的替换方式将括号对替换掉
     * 然后判断字符串是否为空
     */
    public static boolean isValid2(String s) {
        while (s.contains("()")
                || s.contains("[]")
                || s.contains("{}")) {
            s = s.replace("()", "");
            s = s.replace("[]", "");
            s = s.replace("{}", "");
        }
        return s.isEmpty();
    }

    public static void main(String[] args) {
        System.out.println(isValid2("()"));
        System.out.println(isValid2("([)]"));
        System.out.println(isValid2("(){}"));
        System.out.println(isValid2("([])"));
    }
}
